package data_structures_and_algorithms.list_node;

import common.ListNode;

/**
 * @ClassName Code_0142_hsCycleII
 * @Description: https://leetcode.cn/problems/linked-list-cycle-ii/
 * 环形链表II
 *
 * @Author: myl
 * @create_time: 2022/10/27 23:50
 */
public class Code_0142_hsCycleII {

    // 画出图，然后写个推导公式
    // 思路：找到相遇节点后，慢节点回到head，然后fast以每次走一步的速度和slow一样进行，二者终会相遇，相遇点即为入环口
    public ListNode detectCycle(ListNode head) {
        if (head == null || head.next == null)
            return null;
        ListNode slow = head.next, fast = head.next.next;

        while (true){
            if (slow == fast)
                break;
            if (fast == null || fast.next == null)
                return null;
            slow = slow.next;
            fast = fast.next.next;
        }

        slow = head;
        while (slow != fast){
            slow = slow.next;
            fast = fast.next;
        }

        return slow;
    }
}
